package com.fanshuai.algorithms.random;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Random {
    private static java.util.Random random = new java.util.Random(System.currentTimeMillis());
    /**
     * 数组乱序方法。正确随机
     */
    public static void shuffle(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int r = random(i, a.length - 1);
            swap(a, i, r);
        }
    }

    /**
     * 正确随机
     * @param a
     */
    public static void shuffle2(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            int r = random(0, i);
            swap(a, i, r);
        }
    }

    /**
     * 错误随机  部分结果的概率更大
     * @param a
     */
    public static void shuffle3(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int r = random(0, a.length - 1);
            swap(a, i, r);
        }
    }

    /**
     * 错误随机  部分结果的概率更大
     * @param a
     */
    public static void shuffle4(int[] a) {
        for (int i = a.length - 1; i >= 0; i--) {
            int r = random(0, a.length - 1);
            swap(a, i, r);
        }
    }

    private static int random(int start, int end) {
        return start + random.nextInt(end - start + 1);
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 随机结果类
     */
    public static class RandomResult {
        public int[] a;

        public RandomResult(int[] a) {
            this.a = a;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            RandomResult that = (RandomResult) o;
            return Arrays.equals(a, that.a);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(a);
        }

        @Override
        public String toString() {
            return "RandomResult{" +
                    "a=" + Arrays.toString(a) +
                    '}';
        }
    }

    /**
     * 验证随机算法是否正确的方法：
     * 重复验证足够大的次数，统计各个结果出现的次数是否近似相等
     */
    public static void checkRandom() {
        int N = 1000000;

        Map<RandomResult, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int[] a = {1, 2, 3, 4, 5, 6};
            shuffle(a);

            RandomResult r = new RandomResult(a);
            if (map.containsKey(r)) {
                map.put(r, map.get(r) + 1);
            } else {
                map.put(r, 1);
            }
        }

        for (RandomResult r : map.keySet()) {
            System.out.println("result=" + r + ", count=" + map.get(r));
        }
    }

    public static void main(String[] args) {
        checkRandom();
    }
}
